"""
File: sfo_56-i_single_number_i_s1.py
Created Time: 2021-12-09
Author: Krahets (krahets@163.com)
"""

from include import *


# ===== Solution Code =====
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x, y, n, m = 0, 0, 0, 1
        for num in nums:  # 1. 遍历异或
            n ^= num
        while n & m == 0:  # 2. 循环左移，计算 m
            m <<= 1
        for num in nums:  # 3. 遍历 nums 分组
            if num & m:
                x ^= num  # 4. 当 num & m != 0
            else:
                y ^= num  # 4. 当 num & m == 0
        return x, y  # 5. 返回出现一次的数字


# ======= Test Case =======
nums = [4, 1, 4, 6]
# ====== Driver Code ======
slt = Solution()
res = slt.singleNumbers(nums)
print(res)
